package cn._2dland.utils
{
	import cn._2dland.comment.CommentObject;

	/**
	 * 有序双向链表
	 * @author deadblue
	 */	
	public class SortedLinkedList
	{
		private var _compObj:IDataCompareRule = null;

		private var _head:LinkedListNode;
		private var _tail:LinkedListNode;
		private var _curr:LinkedListNode;

		private var _size:int;

		public function SortedLinkedList(compObj:IDataCompareRule) {
			_compObj = compObj;

			_head = new LinkedListNode(_compObj.getMaximum());
			_tail = _head;
			_curr = _head;
			_size = 0;
		}

		/**
		 * 添加一个节点
		 * @param nodeObj - 节点数据
		 */
		public function add(nodeObj:Object):void {
			var node:LinkedListNode = new LinkedListNode(nodeObj);

			for(var n:LinkedListNode=head; n!=null; n=n.next){
				if(_compObj.deepCompare(n.data, node.data) > 0){
					node.next = n;
					node.previous = n.previous;

					if(node.previous != null)
						node.previous.next = node;
					n.previous = node;
					break;
				}
			}
			if(node.previous == null) _head = node;
			_size ++;
			if(_curr == null) _curr = _head;
		}

		/**
		 * 将指针移动到头部
		 */
		public function first():void {
			_curr = _head;
		}

		/**
		 * 将指针移动到尾部
		 */
		public function last():void {
			_curr = _tail.previous;
		}

		/**
		 * 将指针定位到指定的位置
		 * @param data - 参考数据
		 */
		public function seek(data:Object):void {
			if(_head == null) return;
			if(_curr == null) _curr = _head;

			if(_compObj.compare(_curr.data, data) >= 0){
				while(_curr.previous != null && _compObj.compare(_curr.previous.data, data) >= 0)
					_curr = _curr.previous;
			}
			else {
				while(_curr.next != null && _compObj.compare(_curr.next.data, data) < 0)
					_curr = _curr.next;
				if(_curr.next != null) _curr = _curr.next;
			}
		}

		/**
		 * 获取指定位置的所有数据
		 * @param data - 参考数据
		 * @return 数据数组
		 */
		public function getDatas(data:Object):Array {
			var datas:Array = new Array();

			while(_curr!=null && _compObj.compare(_curr.data, data) <= 0){
				datas.push(_curr.data);
				_curr = _curr.next;
			}
			return datas;
		}
	}
}